#include<bits/stdc++.h>

using namespace std;
using ll = long long;
#define endl '\n'

void setup(int *a, int n) {
    //srand(time(NULL));
    for (int i = 0; i < n; i++) {
        a[i] = rand();
    }

}

int a[10000000], c[10000000];

void merge_sort(int *a, int left, int right) {
    if (left >= right) return;
    int mid = (right + left) / 2;
    //a[left,mid]  and a[mid+1,right]
    merge_sort(a, left, mid);
    merge_sort(a, mid + 1, right);
    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right) {
        if (a[i] <= a[j]) {
            c[k++] = a[i++];
        } else {
            c[k++] = a[j++];
        }
    }
    while (i <= mid) c[k++] = a[i++];
    while (j <= right) c[k++] = a[j++];
    copy(c + left, c + right + 1, a + left);
}

void quick_sort(int *a, int left, int right) {
    if (left > right) {
        return;
    }
    int j = right;
    int i = left;
    while (i != j) {
        while (a[j] >= a[left] && i < j)j--;
        while (a[i] <= a[left] && i < j)i++;
        if (i < j) {
            swap(a[i], a[j]);
        }
    }
    swap(a[left], a[j]);
    quick_sort(a, left, j - 1);
    quick_sort(a, j + 1, right);
}


int main() {
    int n = 10000000;
    setup(a, n);
    ll start = clock();
    merge_sort(a,0,n-1);
    //quick_sort(a, 0, n - 1);
    //sort(a, a + n);
    //stable_sort(a,a_n);
    ll end = clock();
    cout << 1.0 * (end - start) / CLOCKS_PER_SEC << endl;

    return 0;
}
//merge_sort 100,000,000 1.56869
//quick_sort 100,000,000 1.85681
//stl_sort 100,000,000 2.02822
//stable_sort 100,000,000 1.94436